🌈 个人主页：十二月的猫-CSDN博客 🔥 系列专栏： 🏀算法启示录

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光 

目录

前言

松弛视角

伪代码展示

三角形理论 

 松弛操作可行性证明

 Bellman-Ford算法

算法思想

1.流程描述

2.流程图解

3.流程阐释

算法伪代码

算法证明 

路径松弛性质

最短路径证明

总结

最短路径算法是图论中一类重要算法，其功能就如名字一样——求解点与点之间最短距离。

首先，先让我们对最短路径算法有一个概观，看看都有哪些种类的最短路径算法，每一个种类中代表的算法又是什么。

单源最短路径算法：从一个起点出发求解其到其他所有其他点的最短距离

多源最短路径算法：从所有点出发求解其到其他所有其他点的最短距离 

关键点：

1、松弛和动态规划都是解决最短路径的方法。

2、松弛的本质就是对图固有属性三角理论的修正。

3、松弛和动态规划方法存在一定的重合，有时可以相互转化。两者并未有固定的优秀等次之分。

4、一些算法采用松弛视角解决，另一些采用动态规划视角来解决

最短路径的求解包含两个步骤：一、初始化操作；二、松弛操作

松弛是最短路径求解过程中最好用的手段之一

两个操作的伪代码如下：

初始化操作：

松弛操作：

松弛操作的本质是对三角形理论的修正 

定义：

对于任何边（u，v）∈E，都有d(s,v)u.d+w(u,v) return FALSE return TRUE RELAX(u,v,w) if v.d>u.d+w(u,v) v.d=u.d+w(u,v) v.π=u 算法证明 

贝尔曼福特算法的证明包括：1、最短路径证明；2、算法返回值完整性证明

这里我们重点来看最短路径证明：1、路径松弛性质；2、最短路径证明

理解关键点： 

1、本性质的成立和松弛操作无关。也就是说这些操作不一定是连续进行的，在彼此之间可以穿插其他的松弛操作。只要按这个相对顺序进行这样一遍松弛处理，那么我们一定能够得到vk的最短路径（即使是在第一轮松弛中，我们就按这个顺序进行松弛，依旧能得到vk的最短路径）

理解关键点： 

1、假如路径长为k，也就是以vk为目的点。由于没有环，所以k小于等于V-1。而我们可以进行V-1次松弛，每次松弛都是对所有边进行的。也就是说第一次松弛必然有（v0，v1），第二次松弛有（v1，v2），第三次则有（v2，v3）以此类推，最后必然可以（因为k小于等于V-1）到（vk-1，vk），也就说vk必然已经得到最短路径。证毕~~

本文到这里就结束啦~~

本篇文章的撰写花了本喵两个多小时

如果仍有不够希望大家多多包涵~~如果觉得对你有帮助，辛苦友友点个赞哦~

知识来源：《算法导论》、山东大学孔凡玉老师ppt。不要用于商业用途转发哦~